package sort;

import java.util.ArrayList;
import java.util.Arrays;

public class HeapSort {
    public static void MaxHeapify(ArrayList<Integer> A, int i,int size) {
        int j = 0;
        for (i = i; 2 * i <= size; i = j) {
            j = 2 * i;
            if (j + 1 <= size && A.get(j) < A.get(j + 1)) {
                j++;
            }
            if (A.get(j) <= A.get(i)) {
                break;
            }
            A.set(0, A.get(j));
            A.set(j, A.get(i));
            A.set(i, A.get(0));
        }


    }

    /**
     * A中0为哨兵
     * @param A；
     */
    public static void BuildMaxHeap(ArrayList<Integer> A){
        for (int i = (A.size()-1)/2; i >=1 ; i--) {
            MaxHeapify(A, i,A.size()-1);
            System.out.println(i);
        }

    }
    public static void BeginSort(ArrayList<Integer> A){
        for (int i = A.size()-2; i >=1 ; i--) {
            A.set(0, A.get(1));
            A.set(1, A.get(i+1));
            A.set(i+1, A.get(0));
            MaxHeapify(A,1,i);
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(){{
            add(0);
            add(5);
            add(8);
            add(1);
            add(4);
            add(2);
            add(3);
            add(9);
            add(10);
            add(7);
            add(14);
            add(16);
        }};
        BuildMaxHeap(list);
        BeginSort(list);
        System.out.println(Arrays.toString(list.toArray()));
    }

}
